今天來解第16題啦~

題目

題目翻譯

給定一個長度為 n 的數字陣列 nums，另外給定一個整數 target，要求從 nums 中選擇三個數字加總，其和是最接近 target

解題思路

1. 初始化變數：

   • 先初始化一個 closest 變數，用來儲存當前找到最接近目標值的三數之和。初始值設為前三個數的和，因為至少有三個數。
   • 初始化 diff 變數，用來儲存當前三數之和與目標值 target 之間的差值（取絕對值）。
   • 將輸入數組進行排序，以便後續使用雙指針方法進行查找。

2. 遍歷數組：

   • 使用一個 for 循環遍歷數組，針對每個元素作為三元組中的第一個元素，並跳過相鄰的重複元素，避免重複計算。

3. 雙指針技術：

   • 在每次循環中，設置兩個指針，left 指向當前元素之後的位置，right 指向數組的末尾。
   • 計算三個數的和 sum，並更新與 target 的差值 newDiff。如果這個新的差值比之前找到的更小，則更新最接近的三數之和 closest。
   • 根據 sum 和 target 的比較，決定是移動 left 指針（如果 sum 小於 target），還是移動 right 指針（如果 sum 大於 target），從而嘗試縮小與目標值的差距。

4. 返回結果：

   • 當循環結束後，返回找到的最接近 target 的三數之和 closest。

code

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        int closest = nums[0] + nums[1] + nums[2];  // 初始最接近值為前三個數的和
        sort(nums.begin(), nums.end());  // 排序數組
        
        for (int i = 0; i < n - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;  // 跳過重複元素
            int left = i + 1, right = n - 1;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                // 如果找到更接近的和，更新 closest
                if (abs(sum - target) < abs(closest - target)) {
                    closest = sum;
                }
                
                if (sum < target) {
                    ++left;  // 和小於目標值，移動左指針
                } else if (sum > target) {
                    --right;  // 和大於目標值，移動右指針
                } else {
                    return sum;  // 如果找到精確等於 target 的和，直接返回
                }
            }
        }
        
        return closest;  // 返回最接近的三數之和
    }
};